package Subject;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 难度：中等
 * 
 * 49.字母异位词分组
 * 	给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * 
 * 示例:
 *	输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 *	输出:
 *	[
 *   ["ate","eat","tea"],
 *   ["nat","tan"],
 *   ["bat"]
 *	]
 *
 * 说明：
 *	所有输入均为小写字母。
 *	不考虑答案输出的顺序。
 *
 * */

public class GroupAnagrams {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		GroupAnagrams ga = new GroupAnagrams();
		String [] strs = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
		System.out.println(ga.groupAnagrams2(strs));
	}
	//方法一：排序
	public ArrayList<List<String>> groupAnagrams1(String[] strs) {
		Map<String,List<String>> map = new HashMap<String,List<String>>();
		for(String str:strs) {
			char[] arts = str.toCharArray();
			Arrays.sort(arts); 
			String key = String.valueOf(arts);
			if(!map.containsKey(key)) {
				map.put(key, new ArrayList<String>());
			}
			map.get(key).add(str);
		}
		return new ArrayList<List<String>>(map.values());
	}
	//方法二：计数
	 public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
//            System.out.println(sb);
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
	
}
